/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import com.vijos.Uitls;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/13
 */
public class _5_239_SlidingWindowMaximum {
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        int pos = -1; // initialize pos = -1
        int[] res = new int[nums.length - k + 1];
        boolean lager;
        for (int i = 0; i < nums.length - k + 1; i++) {
            if (pos >= i) { // compare previous pos with new i
                lager = nums[i + k - 1] >= nums[pos];
                res[i] = lager ? nums[i + k - 1] : nums[pos];
                pos = lager ? i + k - 1 : pos;
            } else { // if previous pos < new i, we have no choice but to traverse the subarray by call findMax
                pos = findMax(nums, i, i + k - 1);
                res[i] = nums[pos];
            }
        }
        return res;
    }

    // traverse the subarray and return the index of its max element
    private static int findMax(int[] nums, int s, int e) {
        int pos = 0, max = Integer.MIN_VALUE;
        for (int i = s; i <= e; i++) {
            if (nums[i] >= max) {
                pos = i;
                max = nums[i];
            }
        }
        return pos;
    }

    public static int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] r = new int[n - k + 1];
        int ri = 0;
        // store index
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // remove numbers out of range k
            while (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            // remove smaller numbers in k range as they are useless
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
                q.pollLast();
            }
            // q contains index... r contains content
            q.offer(i);
            if (i >= k - 1) {
                r[ri++] = nums[q.peek()];
            }
        }
        return r;
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (nums == null || len == 0) {
            return new int[]{};
        }
        Deque<Integer> dq = new ArrayDeque<>();
        int[] result = new int[len - k + 1];
        for (int i = 0; i < len; i++) {
            if (i < k) {
                dq.addLast(nums[i]);
            } else {
                result[i - k] = max(dq);
                dq.pollFirst();
                dq.addLast(nums[i]);
            }
        }
        result[result.length - 1] = max(dq);
        return result;
    }

    public static int max(Deque<Integer> dq) {
        Iterator<Integer> iterator = dq.iterator();
        int max = Integer.MIN_VALUE;
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (max < next) {
                max = next;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Utils.printArray(maxSlidingWindow2(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3));
    }
}
